#include <string>
#include <vector>
#include <cstring>
using namespace std;

class Solution {
private:
    const long long mod = 1000000007;

    // 1. 暴力递归解法
    int f1(const char* s, int i) {
        if (s[i] == '\0') {
            return 1;
        }
        if (s[i] == '0') {
            return 0;
        }
        // 当前字符单独解码
        int ans = f1(s, i + 1) * (s[i] == '*' ? 9 : 1);
        // 与下一个字符一起解码
        if (s[i + 1] != '\0') {
            if (s[i] != '*') {
                if (s[i + 1] != '*') {
                    // 两个都是数字
                    int num = (s[i] - '0') * 10 + (s[i + 1] - '0');
                    if (num <= 26) {
                        ans += f1(s, i + 2);
                    }
                } else {
                    // 第一个是数字，第二个是*
                    if (s[i] == '1') {
                        ans += f1(s, i + 2) * 9;
                    }
                    if (s[i] == '2') {
                        ans += f1(s, i + 2) * 6;
                    }
                }
            } else {
                if (s[i + 1] != '*') {
                    // 第一个是*，第二个是数字
                    if (s[i + 1] <= '6') {
                        ans += f1(s, i + 2) * 2;
                    } else {
                        ans += f1(s, i + 2);
                    }
                } else {
                    // 两个都是*
                    ans += f1(s, i + 2) * 15;
                }
            }
        }
        return ans;
    }

    // 2. 记忆化搜索解法
    long long f2(const char* s, int i, vector<long long>& dp) {
        if (s[i] == '\0') {
            return 1;
        }
        if (s[i] == '0') {
            return 0;
        }
        if (dp[i] != -1) {
            return dp[i];
        }
        
        long long ans = f2(s, i + 1, dp) * (s[i] == '*' ? 9 : 1);
        if (s[i + 1] != '\0') {
            if (s[i] != '*') {
                if (s[i + 1] != '*') {
                    int num = (s[i] - '0') * 10 + (s[i + 1] - '0');
                    if (num <= 26) {
                        ans += f2(s, i + 2, dp);
                    }
                } else {
                    if (s[i] == '1') {
                        ans += f2(s, i + 2, dp) * 9;
                    }
                    if (s[i] == '2') {
                        ans += f2(s, i + 2, dp) * 6;
                    }
                }
            } else {
                if (s[i + 1] != '*') {
                    if (s[i + 1] <= '6') {
                        ans += f2(s, i + 2, dp) * 2;
                    } else {
                        ans += f2(s, i + 2, dp);
                    }
                } else {
                    ans += f2(s, i + 2, dp) * 15;
                }
            }
        }
        
        ans %= mod;
        dp[i] = ans;
        return ans;
    }

public:
    // 1. 暴力解法
    int numDecodings1(string s) {
        return f1(s.c_str(), 0);
    }

    // 2. 记忆化搜索解法
    int numDecodings2(string s) {
        int n = s.size();
        vector<long long> dp(n, -1);
        return (int)f2(s.c_str(), 0, dp);
    }

    // 3. 动态规划解法
    int numDecodings3(string s) {
        int n = s.size();
        vector<long long> dp(n + 1, 0);
        dp[n] = 1;
        
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] != '0') {
                dp[i] = (s[i] == '*' ? 9 : 1) * dp[i + 1];
                
                if (i + 1 < n) {
                    if (s[i] != '*') {
                        if (s[i + 1] != '*') {
                            int num = (s[i] - '0') * 10 + (s[i + 1] - '0');
                            if (num <= 26) {
                                dp[i] += dp[i + 2];
                            }
                        } else {
                            if (s[i] == '1') {
                                dp[i] += dp[i + 2] * 9;
                            }
                            if (s[i] == '2') {
                                dp[i] += dp[i + 2] * 6;
                            }
                        }
                    } else {
                        if (s[i + 1] != '*') {
                            if (s[i + 1] <= '6') {
                                dp[i] += dp[i + 2] * 2;
                            } else {
                                dp[i] += dp[i + 2];
                            }
                        } else {
                            dp[i] += dp[i + 2] * 15;
                        }
                    }
                }
                
                dp[i] %= mod;
            }
        }
        
        return (int)dp[0];
    }

    // 4. 空间优化的动态规划解法
    int numDecodings4(string s) {
        int n = s.size();
        long long cur = 0, next = 1, nextNext = 0;
        
        for (int i = n - 1; i >= 0; i--) {
            cur = 0; // 重置当前值
            if (s[i] != '0') {
                cur = (s[i] == '*' ? 9 : 1) * next;
                
                if (i + 1 < n) {
                    if (s[i] != '*') {
                        if (s[i + 1] != '*') {
                            int num = (s[i] - '0') * 10 + (s[i + 1] - '0');
                            if (num <= 26) {
                                cur += nextNext;
                            }
                        } else {
                            if (s[i] == '1') {
                                cur += nextNext * 9;
                            }
                            if (s[i] == '2') {
                                cur += nextNext * 6;
                            }
                        }
                    } else {
                        if (s[i + 1] != '*') {
                            if (s[i + 1] <= '6') {
                                cur += nextNext * 2;
                            } else {
                                cur += nextNext;
                            }
                        } else {
                            cur += nextNext * 15;
                        }
                    }
                }
                
                cur %= mod;
            }
            
            // 更新状态变量
            nextNext = next;
            next = cur;
        }
        
        return (int)next;
    }
};
